Indirect jump instructions are commonly employed in the increasing number of programs written in object-oriented languages such as C#, Java, and C++. To support polymorphism, these languages include virtual function calls that are implemented using indirect jump instructions in the instruction set architecture of a microprocessor. In addition to virtual function calls, indirect jumps are commonly used in the implementation of programming language constructs such as switch-case statements, jump tables, and interface calls.
Current pipelined processors fall short in predicting the target address of an indirect jump if multiple different targets are exercised at run-time. Such hard-to-predict indirect jumps not only limit processor performance and cause wasted energy consumption but also contribute significantly to the performance difference between traditional and object-oriented languages. A contemplated solution to this shortcoming was to handle indirect jumps by dynamically predicating them. However, dynamic predication of an indirect jump instruction can sometimes degrade performance if predication is not useful.
Current pipelined processors can use branch prediction to improve performance. In practice, predicting a branch instruction correctly allows the processor to continue fetching instructions to fill a microprocessor pipeline without interruptions. Even though branch mispredictions are infrequent with state-of-the-art branch predictors, they are a performance bottleneck because they force the processor to flush the pipeline and restart fetching from the correct path. Also, a result of current practices is energy consumption by the operative microprocessors that, with current practices, are tasked to handle a large number of wrong path instructions. In many cases, a significant portion of the flushed instructions are on the correct path, i.e., control independent instructions that should be executed no matter which direction the branch takes. Therefore, with current solutions, the processor could end up fetching and executing mostly the same instructions after a branch misprediction.
Indirect jumps are control instructions that can be succeeded by a large number of possible next instructions (targets). Operatively, the actual target depends on data that may only be known at runtime. Currently, indirect jumps are predicted using a Branch Target Buffer (BTB), which, operatively, stores the last taken target of every control instruction. However, if the indirect jump has multiple targets that are interleaved at runtime, the BTB-based prediction can generally provide an incorrect prediction. More sophisticated indirect jump predictors have been proposed and deployed to overcome this limitation. Such predictors consider the branch or path history in addition to the address of the jump to produce a more accurate prediction. However, the accuracy of indirect jump predictors is still below that of conditional branch predictors because indirect jumps are inherently more difficult to predict: conditional branches can only have two outcomes (taken or not-taken), while indirect jumps can exercise many targets at runtime.
Traditionally, predication has been proposed as a compiler technique that eliminates conditional branches by converting control dependencies to data dependencies. Operatively, those instructions whose predicate is resolved to be true commit their results to the architectural (software-visible) state of the program. Predicated-false instructions do not change the architectural state (i.e., become no operations (NOPs)). By using software predication, the processor can avoid the pipeline flush that would have been produced by a branch misprediction (i.e., at the cost of fetching the instructions on the wrong-path of the branch). Therefore, if the compiler carefully selects the branches that are predicated, the benefit of predication can overcome the cost of fetching and possibly executing the instructions on the wrong path.
Predication is not without limitations. Specifically, predication requires a fully predicated instruction set architecture (ISA), i.e., visible predicate registers and predicated instructions. Additionally, predication cannot be adaptive to runtime program behavior. That is, if the branch would have been easy-to-predict, the cost of fetching and executing the wrong path is incurred by the processor.
From the foregoing it is appreciated that there exists a need for systems and methods to ameliorate the shortcomings of existing practices.